package problem491;

import java.util.ArrayList;
import java.util.List;

//491.非递减子序列
//https://leetcode.cn/problems/non-decreasing-subsequences/description/?envType=problem-list-v2&envId=hash-table

class Solution {
    List<Integer> list;
    List<List<Integer>> ret;
    public List<List<Integer>> findSubsequences(int[] nums) {
        list = new ArrayList<>();
        ret = new ArrayList<>();
        dfs(nums,Integer.MIN_VALUE, 0);
        return ret;
    }

    private void dfs(int[] nums,int pre, int u) {
        if(u == nums.length) {
            if(list.size() > 1) {
                ret.add(new ArrayList<>(list));
            }
            return;
        }
        //选
        if(nums[u] >= pre) {
            list.add(nums[u]);
            dfs(nums, nums[u], u+1);
            list.remove(list.size()-1);
        }
        //不选
        if(nums[u] != pre) {
            dfs(nums,pre, u+1);
        }
    }
}